1. Field of the Invention
The present invention relates to a scheme for data transfer among data communication devices which are interconnected through a network.
2. Description of the Background Art
In the data exchange among data communication devices which are interconnected through a network, some data exchanges are strongly dependent on an arrival order of data to be exchanged, and there are cases in which it is required to uniquely specify an order of exchanges among a plurality of data communication devices.
For example, consider a case of a network system as shown in FIG. 1 which is formed by three data communication devices A, B and C interconnected through a network. In this network system of FIG. 1, the data communication devices A, B and C have data of identical contents which are copied at each device, and an updating of data is realized by rewriting data at one device and notifying entered modifications to other devices so that each of the other devices updates the own data according to the notified modifications. In this manner, the data contents owned by the data communication devices A, B and C are maintained consistently.
This scheme is widely used because an amount of data to be exchanged is rather small. FIGS. 2A and 2B illustrates this scheme. Namely, an event X: "write a circle" made by one user at the device A is transmitted to the other devices B and C as shown in FIG. 2A, so that data owned by all the devices A, B and C are updated as shown in FIG. 2B.
However, this data updating is carried out simultaneously in parallel at each data communication device so that if the updating is not carried out in a unique time order, that is, if the arrival order of packets indicating the modifications are different at different devices, the data contents owned by different devices may turn out to be different as illustrated in FIGS. 3A and 3B.
Namely, in FIG. 3A, an event Y: "move a region enclosing a circle" at the device A and an event Z: "write a cross on a current position of a circle" at the device B are simultaneously made and transmitted to the respective other devices. When the data representing these events are straightforwardly processed in their arrival order, since the locally received event arrives first, the arrival orders at the devices A, B and C are:
Event Y, Event Z at the device A,
Event Z, Event Y at the device B, and
Event Z, Event Y at the device C, for example, and therefore if these events are processed in such an arrival order at each device, the data at the device A would be different from the data at the device B and the device C as shown in FIG. 3B.
On the other hand, a method for updating the own data at each device can be largely classified into the following three types:
(i) a method for updating the own data first, and then transmitting modifications to the others (without confirming the transmission completion); PA1 (ii) a method for updating the own data first, and then transmitting modifications to the others. If the transmission completion is not confirmed, the own data is restored; and PA1 (iii) a method for transmitting modifications to the others first, and then the own data is updated when the transmission completion is confirmed. PA1 (I) a scheme for synchronizing time among the data communication devices and transmitting a data packet by attaching a transmission time thereto so that each data packet becomes unique in time; PA1 (II) a scheme in which a data packet is transmitted from each data communication device to a server once, and then data packets are ordered at the server and transmitted from the server to the data communication devices, so as to maintain the uniqueness; PA1 (III) a scheme in which a token is issued at each data communication device, and sequentially moved to another device at a constant time interval. Each data communication device can transmit a data packet only while it possesses the token, so as to maintain the uniqueness.
In the method (i), the data updating and the modifications transmission at the own device are given a priority, and states of the other devices are ignored.
In the method (ii), the data updating and the modifications transmission at the own device are given a higher priority, but invalidated when the other devices failed to receive the modifications.
In the method (iii), the updating becomes possible only after the receiving of the modifications by the other devices is confirmed, so that data arrives at every device, although the data arrival order is not certain. The examples illustrated in FIGS. 2A, 2B, 3A and 3B are based on the method (i), but even when the method (ii) or the method (iii) is employed, the similar situation as described above can happen.
As a scheme for preventing such a difference in data among a plurality of devices and maintaining the arrival order uniquely, various schemes have been proposed and utilized, including the following:
The scheme (I) is associated with the problems of: (1) how to synchronize time; and (2) how to handle data packets which are transmitted at the identical time by a plurality of different data communication devices (even when these data packets are transmitted at not exactly the same time, this situation also occurs if there is a delay in the actual transmission timing due to the re-transmission, etc.
The scheme (II) is associated with the following problems. (1) In view of the processing load on the server, the server is required to have a superior processing power than the data communication devices. (2) In a straightforward comparison with a case of transmission from a source device to the other devices, it is necessary to use a transmission path which is twice as long, and this straightforwardly implies that traffic becomes twice as large. (3) Information concerning the data packet order is centrally managed by the server, so that there is a need to provide a measure (such as saving of data managed by the server) for dealing with a trouble in anticipation of an accident such as a sudden loss of the server.
The scheme (III) is associated with the problems of: (1) a recovery processing in a case of token loss; and (2) an increase of communication cost due to communications for token exchange.
As a scheme for resolving these problems of these conventionally known schemes, the present inventor has previously proposed a scheme in which one device regularly transmits an information on an order of packets received at that device to the other devices, and these other devices rearrange the processing order for the respective received packets according to this packet order information before processing the packets, as disclosed in Japanese Patent Application No. 7-321871 (1995). However, according to this scheme, the received packet cannot be processed until the packet order information is obtained, so that it is necessary to obtain the packet order information even in an ordinary state in which the packet order variation is small. Consequently, although it is possible to deal with a sudden packet order variation by the handling similar to that in an ordinary state, it in turn causes the lowering of a response in an ordinary state.
Thus, the prior art schemes for maintaining the data packet order uniquely have been associated with various problems such as an increase of communication cost or response delay in an ordinary state, or a centralized processing load and a high cost required at a time of recovery from a trouble as a result of the centralized processing load.